package com.love.labuladong.stack;

/**
 * @Author : zh
 * @Description :
 * @Date : 2024-08-26 19:20
 */
public class SingleStack {


    public static int MAXN = 1000001;

    public static int[] arr = new int[MAXN];

    public static int[] stack = new int[MAXN];

    public static int[][] ans = new int[MAXN][2];

    public static int n, r;


    // arr[0...n-1]
    public static void compute(){
        r = 0;
        int cur;
        for(int i = 0; i < n; i++){
            // i -> arr[i]
            while ( r > 0 && arr[stack[r - 1]]  >= arr[i]){
                cur = stack[--r];
                // cur 当前弹出的位置，左边最近且最小
                ans[cur][0] = r > 0 ? stack[r - 1] : -1;
                ans[cur][1] = i;
            }
            stack[r++] = i;
        }
        // 清算阶段
        while (r > 0){
            cur = stack[--r];
            ans[cur][0] = r > 0 ? stack[r - 1] : -1;
            ans[cur][1] = -1;
        }
        // 修正阶段
        // 左侧的答案不需要修正一定是正确的，只有右侧的答案需要修正
        // 从右往左修正，n-1位置的右侧答案一定是-1，不需要修正
        for (int i = n-2; i >= 0; i--) {
            // 答案上的数值和我本身一样
            if(ans[i][1] != -1 && arr[ans[i][1]] == arr[i]){
                ans[i][1] = ans[ans[i][1]][1];
            }
        }
    }


}
